// https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 寻找下一个字典序更大的排列
// 2. 从右向左找到第一个下降位置i（nums[i] < nums[i+1]）
// 3. 在i右侧找到大于nums[i]的最小数字位置j
// 4. 交换nums[i]和nums[j]
// 5. 将i+1到末尾的序列反转（变为最小字典序）
// 6. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    void nextPermutation(vector<int>& nums) 
    {
        int m = nums.size();

        int i = m - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
        {
            i--;
        }

        if (i >= 0)
        {
            int j = m - 1;
            while (nums[j] <= nums[i])
            {
                j--;
            }
            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());

        return ;
    }
};

int main()
{
    vector<int> nums1 = {1,2,3}, nums2 = {3,2,1};
    Solution sol;

    sol.nextPermutation(nums1);
    sol.nextPermutation(nums2);

    for (const int& num : nums1)
        cout << num << " ";
    cout << endl;

    for (const int& num : nums2)
        cout << num << " ";
    cout << endl;

    return 0;
}